%!TEX program = xelatex
%!TEX encoding = UTF-8 Unicode

\documentclass[10pt,a4paper]{article} 

\usepackage{ctex} % 中文支持
\usepackage[top=2.5cm, bottom=2.5cm, left=2.5cm, right=2.5cm]{geometry} % 页边距
\usepackage{amsmath, amssymb} % 数学公式与符号
\usepackage{graphicx}

\usepackage{pythonhighlight}
\usepackage{url} 

\usepackage{tikz}
\usetikzlibrary{graphs,arrows.meta}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{titling}
\setlength{\droptitle}{-2cm} % 标题上移

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%文档的题目、作者与日期
\author{五六七 }
\title{固定起点的最短路算法 }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

\maketitle

\begin{abstract}
在一个有向图中，给定起点和终点，经过什么路线使得路程最短。
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\setcounter{tocdepth}{2}
%\renewcommand\contentsname{目录}
%
%\renewcommand {\baselinestretch} {1.3}\normalsize 
%\tableofcontents 
%\renewcommand {\baselinestretch} {1.0}\normalsize


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{问题描述}
某人要从顶点$v_1$出发去旅行，目的地与交通路线如图所示。
求该旅行者到目的地$v_8$的旅行路线，使得费用最小。

%\begin{center}
%\begin{tikzpicture}[auto]

\begin{center}
\begin{tikzpicture}[
>={Stealth[length=3mm,width=3mm]}, % 设置更大的箭头尺寸
shorten >= 1pt, % 短化起点，防止箭头与节点重合
auto,
node distance=3cm,
thick,
main node/.style={circle,draw,font=\sffamily\Large\bfseries}
]

\node [circle,draw] (s1) at (0,0) {1}; 
\node [circle,draw] (s2) at (3,2) {2}; 
\node [circle,draw] (s3) at (3,0) {3}; 
\node [circle,draw] (s4) at (3,-2) {4}; 
\node [circle,draw] (s5) at (6,2) {5}; 
\node [circle,draw] (s6) at (6,-2) {6}; 
\node [circle,draw] (s7) at (10,-2) {7}; 
\node [circle,draw] (s8) at (13,0) {8}; 
\node [circle,draw] (s9) at (10,2) {9}; 
%\node [circle,draw] (s6a) at (7,0) {6a}; 

\draw (s1) to node {6} node [swap]{} (s2);
\draw (s1) to node {3} node [swap]{} (s3);
\draw (s1) to node {} node [swap]{1} (s4);
\draw (s3) to node {2} node [swap]{} (s2);
\draw (s3) to node {} node [swap]{2} (s4);
\draw (s2) to node {1} node [swap]{} (s5);
\draw (s5) to node {} node [swap]{6} (s4);
\draw (s4) to node {10} node [swap]{} (s6);
%\draw (s5) to node {} node [swap]{4} (s6);
%\draw (s6) to node {10} node [swap]{} (s5);
%\draw (s6) to node {5} node [swap]{} (s6a);
%\draw (s6a) to node {5} node [swap]{} (s5);
\draw (s9) to node {} node [swap]{2} (s5);
\draw (s9) to node {3} node [swap]{} (s8);
\draw (s5) to node {} node [swap]{6} (s8);
\draw (s5) to node {3} node [swap]{} (s7);
\draw (s6) to node {2} node [swap]{} (s7);
\draw (s7) to node {4} node [swap]{} (s8);

\graph {(s1) -> (s2)};
\graph {(s1) -> (s3)};
\graph {(s1) -> (s4)};
\graph {(s3) -> (s2)};
\graph {(s3) -> (s4)};
\graph {(s2) -> (s5)};
\graph {(s5) -> (s4)};
\graph {(s4) -> (s6)};
\graph {(s4) -- (s5)};
%\graph {(s5) -> (s6)};

\path[->] (s5) edge[bend right] node[right] {4} (s6);
\path[->] (s6) edge[bend right] node[right] {10} (s5);
%\graph {(s6) -> (s5)};
%\graph {(s6) -> (s6a)};
%\graph {(s6a) -> (s5)};
\graph {(s9) -> (s5)};
\graph {(s9) -> (s8)};
\graph {(s5) -> (s8)};
\graph {(s5) -> (s7)};
\graph {(s6) -> (s7)};
\graph {(s7) -> (s8)};

\end{tikzpicture}
\end{center}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{建立模型}

我们首先把这个赋权有向图的邻接矩阵写出来，其中无法直接到达的两个顶点之间的距离为无穷大，每个顶点到自己的距离为零。
\begin{eqnarray}
W= \begin{pmatrix}
0 & 6 & 3 & 1 & \infty & \infty & \infty & \infty & \infty  \\ 
\infty & 0 & \infty & \infty & 1 & \infty & \infty & \infty & \infty  \\ 
\infty & 2 & 0 & 2 & \infty & \infty & \infty & \infty & \infty  \\ 
\infty & \infty & \infty & 0 & \infty & 10 & \infty & \infty & \infty  \\ 
\infty & \infty & \infty & 6 & 0 & 4 & 3 & 6 & \infty  \\ 
\infty & \infty & \infty & \infty & 10 & 0 & 2 & \infty & \infty  \\ 
\infty & \infty & \infty & \infty & \infty & \infty & 0 & 4 & \infty  \\ 
\infty & \infty & \infty & \infty & \infty & \infty & \infty & 0 & \infty  \\ 
\infty & \infty & \infty & \infty & 2 & \infty & \infty & 3 & 0  \\ 
\end{pmatrix}. 
\end{eqnarray}

\section{Dijkstra算法}
对任意顶点 $v\in V=\{1,2,3,\cdots, 9\}$, 我们定义两个标号和一个永久顶点集：
\begin{eqnarray*}
\ell(v) &=& \text{从起点$v_1$到顶点$v$的当前路径的长度，} \\ 
z(v) &=& \text{顶点 $v$的父顶点，用以记录最短路的路线，} \\ 
S_i &=& \text{第$i$次迭代时的永久顶点集。}
\end{eqnarray*}

\newpage 

Dijkstra的算法如下：

\begin{minipage}{0.9\textwidth}
\vspace{0.2cm}
\makebox[\linewidth]{\rule{\textwidth}{0.5pt}}
\begin{enumerate}
\item  令 $\ell(v_1)=0$, 对 $v\neq v_1$, 令 $\ell(v)=\infty$. 令 $S_0=\{v_1\}$. 令 $i=0$. 
\item  
\begin{enumerate}
\item[2.1.]  对每个 $v\in V-S_i$, 令 $\ell(v)=\min\limits_{u\in S_i} \{ \ell(v), \ell(u)+w(u,v)\}$, 其中$w(u,v)$ 表示从顶点 $u$ 到顶点 $v$ 的距离。
\item[2.2.]  如果通过顶点$u$ 可以使得到达 $v$ 的距离更短，那么更新 $v$ 的父顶点 $z(v)$为 $u$. 
\item[2.3.]  计算$\min\{\ell(v): v\in V-S_i\}$, 设最小值由 $\ell(v_{n_i})$ 达到，则把顶点 $v_{n_i}$ 放入永久集，即 $S_{i+1}=S_i\cup \{v_{n_i}\}$. 
\end{enumerate}
\item  若 $i=8$ 或者 $v_8$ 进入 $S_i$ 则算法终止，否则用 $i+1$ 代替 $i$, 转第2步。
\end{enumerate}
\makebox[\linewidth]{\rule{\textwidth}{0.5pt}}
\vspace{0.2cm}
\end{minipage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{编程计算}
\subsection{手工编程实现Dijkstra算法}

%\begin{lstlisting}[language={Python}]
\begin{python}
import numpy as np
aa=np.inf
R1=[0, 6, 3, 1, aa, aa, aa, aa, aa]
R2=[aa, 0, aa, aa, 1, aa, aa, aa, aa]
R3=[aa, 2, 0, 2, aa, aa, aa, aa, aa]
R4=[aa, aa, aa, 0, aa, 10, aa, aa, aa]
R5=[aa, aa, aa, 6, 0, 4, 3, 6, aa]
R6=[aa, aa, aa, aa, 10, 0, 2, aa, aa]
R7=[aa, aa, aa, aa, aa, aa, 0, 4, aa]
R8=[aa, aa, aa, aa, aa, aa, aa, 0, aa]
R9=[aa, aa, aa, aa, 2, aa, aa, 3, 0]


W=np.array([R1,R2,R3,R4,R5,R6,R7,R8,R9])

ell=[aa,aa,aa,aa,aa,aa,aa,aa] # Current shortest lengths from vertex 1 
zzz=[0,0,0,0,0,0,0,0] # Current parent vertex of each vertex
V={0,1,2,3,4,5,6,7} # The set of all vertices 
S={0} # Current permanent vertices 

for ii in range(8):
    print('Permanent vertices: ',S)
    print('Current shortest length: ',ell)
    print('Parent vertex: ', zzz)
    print('\n')    
    for u in S:
        for v in V-S:
            if ell[u]+W[u,v]<ell[v]:
                zzz[v]=u
                ell[v]=ell[u]+W[u,v]
    temp=aa
    ni=0
    for k in V-S:
        if ell[k]<temp:
            ni=k
            temp=ell[k]
    S.add(ni)
\end{python}
%\end{lstlisting}

%\newpage 
\subsection{使用networkx库函数计算最短路}

\begin{python}
# Example 6-7
import networkx as nx

G = nx.DiGraph()
List = [(1,2,6), (1,3,3), (1,4,1), (2,5,1), (3,2,2), (3,4,2), (4,6,10), (5,4,6),
        (5,6,4), (5,7,3), (5,8,6), (6,5,10), (6,7,2), (7,8,4), (9,5,2), (9,8,3)]

G.add_nodes_from(range(1,10))
G.add_weighted_edges_from(List)

path = nx.dijkstra_path(G, 1, 8, weight='weight')  #Find the shortest path 
d = nx.dijkstra_path_length(G, 1, 8, weight='weight')

print('The shortest path is: ', path)
print('The minimal cost is: ', d)  
\end{python}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{回答问题}

从顶点1到顶点8的最短路径为 $v_1\to v_3 \to v_2 \to v_5 \to v_8, $
最小费用为12. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section{参考文献 }
\begin{thebibliography}{99}
\bibitem{sishoukui-2} 司守奎,孙玺菁. \emph{Python数学建模算法与应用}, 国防工业出版社. 2022年1月第1版. 
\bibitem{rosen-dm6}Kenneth H. Rosen 著, 袁崇义, 屈婉玲, 张桂芸等译. \emph{离散数学及其应用}, 机械工业出版社，2013年4月第1版。
\end{thebibliography}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


